/*
Merge two sorted linked lists and return it as a new list. 
The new list should be made by splicing together the nodes of the first two lists.
*/
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

struct ListNode
{
   int val;
   ListNode *next;
   ListNode(int x) : val(x), next(NULL) {}
};
//9ms
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
{
    if (l1 == nullptr && l2 == nullptr) {
        return nullptr;
    } else if (l1 == nullptr && l2 != nullptr) {
        return l2;
    } else if (l1 != nullptr && l2 == nullptr) {
        return l1;
    } else {}
    
    ListNode * head = new ListNode(-1), * curr = nullptr;
    curr = head;
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val <= l2->val) {
            curr->next = l1;
            l1 = l1->next;
        } else {
            curr->next = l2;
            l2 = l2->next;
        }
        curr = curr->next;
    }
    while (l1 != nullptr) {
        curr->next = l1;
        l1 = l1->next;
        curr = curr->next;
    }
    while (l2 != nullptr) {
        curr->next = l2;
        l2 = l2->next;
        curr = curr->next;
    }
    return head->next;
}
//13ms
// void recur(ListNode * rst, ListNode * l1, ListNode * l2)
// {
//     if (l1 == nullptr && l2 != nullptr) {
//         rst->next = l2;
//         return;
//     } else if (l1 != nullptr && l2 == nullptr) {
//         rst->next = l1;
//         return;
//     } else if ( l1 == l2 && l1 == nullptr) {
//         return;
//     } else {
//         if (l1->val >= l2->val) {
//             rst->next = l2;
//             recur(rst->next, l1, l2->next);
//         } else {
//             rst->next = l1;
//             recur(rst->next, l1->next, l2);
//         }
//     }
// }

// ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
// {
//     if (l1 == nullptr && l2 == nullptr) {
//         return nullptr;
//     } else if (l1 == nullptr && l2 != nullptr) {
//         return l2;
//     } else if (l1 != nullptr && l2 == nullptr) {
//         return l1;
//     } else {}
    
//     ListNode * head = new ListNode(-1);
//     recur(head, l1, l2);
//     return head->next;
// }

int main(int argc, const char * argv[])
{
    ListNode * l1 = new ListNode(2);
    ListNode * l2 = new ListNode(1);
    mergeTwoLists(l1, l2);
    return 0;
}
